package jago02.jago0201.ag01_sort;

import java.util.Arrays;

/**
 * 归并排序
 * 杂化简：采用分治算法，将原数组反复对半向下拆分成最小左右子数组，然后向上合并排序左右子数组
 * 解目录：
 *      0.将原数组反复对半向下拆分成最小左右子数组，拆分范围是low-high,默认Low=0,high=数组长度-1
 *      1.子数组继续拆分，左子数组范围为low-mid(low+(high-low)/2),和右子数组范围mid+1--high
 *      2.拆分完成后归并左右子数组，归并时借用临时数组，将low-high范围的原数组，分别比较左右子数组每个元素，然后重新排序
 *      3.比较左右子数组方法：左数组从low开始到mid结束，右数组从mid+1开始到high结束，各从第0个元素开始比较，小的放到临时数组
 * 复杂度：O(NLogN)
 */
public class Sort05_Merge {
    //归并需要的辅助数组
    private static Comparable[]assistArr;

    public static void main(String[] args) {
        Comparable[] arr = new Comparable[]{1,5,2,3,4,6,8,0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(Comparable[] arr) {
        //初始化辅助数组
        assistArr = new Comparable[arr.length];
        //2-定义low和high，分别记录数组中最小的索引和最大的索引
        int low = 0;
        int high = arr.length-1;
        //3-调用sort重载方法完成数组arr中，从索引low到high的元素排序
        sort(arr,low,high);
    }

    private static void sort(Comparable[] arr, int low, int high) {
        if (high<=low){
            return;
        }
        int mid = low+(high-low)/2;
        //拆分成左右，分别排序
        sort(arr,low,mid);
        sort(arr,mid+1,high);
        //左右数组合并
        merge(arr,low,mid,high);
    }

    private static void merge(Comparable[] arr, int low, int mid, int high) {
        //定义三个指针
        int i = low;
        int p1 = low;
        int p2 = mid+1;
        //挨个比较左右数组，从小到大的放到辅助数组
        while (p1<=mid&& p2<=high){
            if (lessThan(arr[p1],arr[p2])){
                assistArr[i++] = arr[p1++];
            }else{
                assistArr[i++] = arr[p2++];
            }
        }
        //此时p1/p2总有一个到头了，没到头的追加到辅助数组即可
        while (p1<=mid){
            assistArr[i++] = arr[p1++];
        }
        while (p2<=high){
            assistArr[i++] = arr[p2++];
        }
        //将辅助数组内容拷贝到原数组
        for (int j=low;j<=high;j++){
            arr[j]=assistArr[j];
        }
    }

    private static void exch(Comparable[] arr, int j, int i) {
        Comparable tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    private static boolean lessThan(Comparable m, Comparable n) {
       return m.compareTo(n)<0;
    }
}
